package com.xdja.uac;

import java.util.LinkedList;
import java.util.List;

/**
 * Author:kongguoguang
 * Date:2020/6/2
 * Time:16:34
 * Summary:
 */
public class JosephusUtil {

    public static void main(String[] args) {
        doJosephus(10, 3);
    }

    /**
     * @param totalNumber 总人数
     * @param triggerNumber 触发离席的报数
     * 大概思路：用一个list保存所有人的编号，每报一轮数就从list里面删除一个元素，直到list里面只剩下一个元素
     * 问题的关键在于如何确定每一轮报数结束后要删除的元素。这里用两个变量startPosition和endPosition分别
     * 表示每一轮开始报数和结束报数的人在List中的位置，则可以得到一个公式：
     * endPosition  = (startPosition + triggerNumber) % list.size() - 1
     * 如果endPosition < 0则说明要删除的元素恰好是list中最后一个元素
     */
    public static void  doJosephus(int totalNumber, int triggerNumber){
        if (totalNumber <= 0 || triggerNumber <= 0){
            System.out.println("param error");
            return;
        }

        System.out.println("共有" + totalNumber + "人， 报到" + triggerNumber + "的人离席");

        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= totalNumber; i++){
            list.add(i);
        }

        //开始报数的元素位置
        int startPosition = 0;

        //结束报数的元素位置
        int endPosition;

        while (list.size() > 1){
            int size = list.size();
            endPosition  = (startPosition + triggerNumber) % size - 1;
            if (endPosition < 0){
                //要删除的元素是list中最后一个元素，下一轮应从0开始
                endPosition = size - 1;
                startPosition = 0;
            } else {
                //要删除的元素不是list中最后一个元素，下一轮应从endPosition开始
                startPosition = endPosition;
            }
            System.out.println("编号为" + list.get(endPosition) + "的人离席");
            list.remove(endPosition);
        }

        System.out.println("最后一个在座的成员编号为" + list.get(0));
    }
}
